Spectral Clustering via Graph Filtering: Consistency on the High-Dimensional Stochastic Block Model

摘要

Spectral clustering is amongst the most popular methods for communitydetection in graphs. A key step in spectral clustering algorithms is theeigen-decomposition of the $n{\times}n$ graph Laplacian matrix to extract its$k$ leading eigenvectors, where $k$ is the desired number of clusters among $n$objects. This is prohibitively complex to implement for very large datasets.However, it has recently been shown that it is possible to bypass theeigen-decomposition by computing an approximate spectral embedding throughgraph filtering of random signals. In this paper, we prove that spectralclustering performed via graph filtering can still recover the planted clustersconsistently, under mild conditions. We analyse the effects of sparsity,dimensionality and filter approximation error on the consistency of thealgorithm.